package 单周赛.history;

import java.util.Arrays;

/**
 *
 */
public class 第323场单周赛 {

    public static void main(String[] args) {

        System.out.println(deleteGreatestValue(new int[][]{{1, 2, 4}, {3, 3, 1}}));

        System.out.println(longestSquareStreak(new int[]{4}));

        Allocator allocator = new Allocator(10);
        allocator.allocate(1, 1);
        allocator.allocate(1, 2);
        allocator.allocate(1, 3);
        allocator.free(2);
        System.out.println(Arrays.toString(allocator.local));

        System.out.println(Arrays.toString(new 第323场单周赛().maxPoints(new int[][]{
                        {1, 2, 3}, {2, 5, 7}, {3, 5, 1}},
                new int[]{5, 6, 2})));
    }

    /**
     * 排序+模拟
     *
     * @param grid
     * @return
     */
    public static int deleteGreatestValue(int[][] grid) {
        int ans = 0;
        for (int[] ints : grid) {
            Arrays.sort(ints);
        }
        for (int i = 0; i < grid[0].length; i++) {
            int max = grid[0][i];
            for (int j = 0; j < grid.length; j++) {
                max = Math.max(max, grid[j][i]);
            }
            ans += max;
        }

        return ans;
    }

    /**
     * 排序+二分
     *
     * @param nums
     * @return
     */
    public static int longestSquareStreak(int[] nums) {
        int ans = -1;
        Arrays.sort(nums);
        int[] dp = new int[nums.length];
        dp[0] = 1;

        for (int i = 1; i < nums.length; i++) {
            int left = 0, right = i - 1;
            int target = -1;

            while (left <= right) {
                int mid = left + (right - left) / 2;
                if (nums[mid] * nums[mid] == nums[i]) {
                    target = mid;
                    break;
                } else if (nums[mid] * nums[mid] > nums[i]) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            }
            dp[i] = 1;
            if (target != -1) {
                dp[i] = dp[target] + 1;
                ans = Math.max(ans, dp[i]);
            }
        }
        return ans;
    }

    /**
     * 排序+动态规划+二分
     */
    static class Allocator {

        int[] local;

        public Allocator(int n) {
            local = new int[n];
            Arrays.fill(local, 1001);
        }

        public int allocate(int size, int mID) {
            int left = 0;
            while (left < local.length) {
                while (left < local.length && local[left] != 1001) {
                    left++;
                }
                if (left != local.length) {
                    int right = left + 1;
                    while (right < local.length && local[right] == 1001) {
                        right++;
                    }

                    if (right - left >= size) {
                        for (int i = 0; i < size; i++) {
                            local[left + i] = mID;
                        }
                        return left;
                    }
                    left = right;
                }
            }
            return -1;
        }

        public int free(int mID) {
            int count = 0;
            for (int i = 0; i < local.length; i++) {
                if (local[i] == mID) {
                    local[i] = 1001;
                    count++;
                }
            }
            return count;
        }
    }

    private int cnt = 0;

    private int[][] direction = new int[][]{{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

    /**
     * 深度优先搜索（超时）
     */
    public int[] maxPoints(int[][] grid, int[] queries) {
        int[] ans = new int[queries.length];
        for (int i = 0; i < queries.length; i++) {
            cnt = 0;
            dfs(grid, new boolean[grid.length][grid[0].length], 0, 0, queries[i]);
            ans[i] = cnt;
        }
        return ans;
    }

    private void dfs(int[][] grid, boolean[][] record, int row, int column, int max) {
        if (record[row][column] || grid[row][column] >= max) {
            return;
        }
        cnt++;
        record[row][column] = true;
        for (int[] direct : direction) {
            int nextRow = row + direct[0];
            int nextColumn = column + direct[1];
            if (nextRow < grid.length && nextRow >= 0 &&
                    nextColumn < grid[0].length && nextColumn >= 0) {
                dfs(grid, record, nextRow, nextColumn, max);
            }
        }
    }
}
